// Created by WXX on 2021/3/2 19:23
#include <iostream>
#include <cstring>

using namespace std;

/**
 * 执行用时：4 ms, 在所有 C++ 提交中击败了73.48%的用户
 * 内存消耗：8.1 MB, 在所有 C++ 提交中击败了25.00%的用户
 */
class MapSum {
public:

    struct Node {
        Node *son[26];
        int v, s;

        Node() {
            for (int i = 0; i < 26; i++) son[i] = NULL;
            v = s = 0;
        }
    } *root;

    void add(string key, int val, int last) {
        auto p = root;
        for (auto c : key) {
            int u = c - 'a';
            if (!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
            p->s += val - last;
        }
        p->v = val;
    }

    Node* query(string key) {
        auto p = root;
        for (auto c : key) {
            int u = c - 'a';
            if (!p->son[u]) return new Node();
            p = p->son[u];
        }
        return p;
    }

    MapSum() {
        root = new Node();
    }

    void insert(string key, int val) {
        add(key, val, query(key)->v);
    }

    int sum(string prefix) {
        return query(prefix)->s;
    }
};

int main() {

    MapSum t = MapSum();
    t.insert("apple", 3);
    cout << t.sum("ap") << endl;  // 3
    t.insert("app", 2);
    cout << t.sum("ap") << endl;  // 5

    return 0;
}
